"""
题目：给定单链表头节点和整数 k（k≥1 且k不大于链表长度），反转链表的前k个节点，返回反转后的链表头节点。
具体见尾部示例
"""


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_first_k_nodes(head, k):
    """反转链表的前k个节点，k不大于链表长度"""
    # 特殊情况：k=1（无需反转）或空链表
    if k == 1 or not head:
        return head
    prev = None  # 前驱节点
    current = head  # 当前节点
    count = 0  # 计数，记录已反转的节点数
    # 反转前k个节点
    while current and count < k:
        next_node = current.next  # 保存下一个节点 防止后续操作丢失链表连接；
        current.next = prev  # 反转指针 将current的next指针指向prev，完成当前节点的指针反转；
        prev = current  # 前驱节点后移 然后将prev后移为current，current后移为next_node，同时count加 1，持续执行直到完成 k 个节点的反转。
        current = next_node  # 当前节点后移
        count += 1
        #count执行完上面的count+=1 就标志着前count个节点已经完成了反转
    # 反转后，原头节点（现在是第k个节点）的next指向未反转的部分（current）
    head.next = current
    # prev是反转后的新头节点（原第k个节点） 而prev此时指向的是原第 k 个节点，也就是反转后的新头节点，最终返回prev。
    return prev


def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


def traverse_linked_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result


# 测试
if __name__ == "__main__":
    # 测试1：反转前3个节点（链表长度5）
    head1 = create_linked_list([1, 2, 3, 4, 5])
    new_head1 = reverse_first_k_nodes(head1, 3)
    print(traverse_linked_list(new_head1))  # 输出: [3, 2, 1, 4, 5]

    # 测试2：反转前1个节点（无需反转）
    head2 = create_linked_list([1, 2, 3])
    new_head2 = reverse_first_k_nodes(head2, 1)
    print(traverse_linked_list(new_head2))  # 输出: [1, 2, 3]

    # 测试3：反转整个链表（k等于链表长度）
    head3 = create_linked_list([1, 2, 3, 4])
    new_head3 = reverse_first_k_nodes(head3, 4)
    print(traverse_linked_list(new_head3))  # 输出: [4, 3, 2, 1]